/*
 * @lc app=leetcode.cn id=264 lang=cpp
 *
 * [264] 丑数 II
 *
 * https://leetcode-cn.com/problems/ugly-number-ii/description/
 *
 * algorithms
 * Medium (58.30%)
 * Likes:    875
 * Dislikes: 0
 * Total Accepted:    120.3K
 * Total Submissions: 206.1K
 * Testcase Example:  '10'
 *
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 *
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 *
 *
 * 示例 2：
 *
 *
 * 输入：n = 1
 * 输出：1
 * 解释：1 通常被视为丑数。
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1
 *
 *
 */

// @lc code=start
#include <unordered_set>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
class Solution
{
public:
    int nthUglyNumber(int n)
    {
        vector<int> factors = {2, 3, 5};
        unordered_set<long> hash;
        priority_queue<long,vector<long>,greater<long>> heap;
        hash.insert(1L);
        heap.push(1L);
        int ugly=0;
        for(int i=0;i<n;++i){
            long cur=heap.top();
            heap.pop();
            ugly=(int)cur;
            for(int factor:factors){
                long next=cur*factor;
                if(!hash.count(next)){
                    hash.insert(next);
                    heap.push(next);
                }
            }
        }
        return ugly;
    }
};
// @lc code=end
